{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Candy Crush"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: candyCrush"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #粉碎糖果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这个问题是实现一个简单的消除算法。</p>\n",
    "\n",
    "<p>给定一个&nbsp;<code>m x n</code>&nbsp;的二维整数数组 <code>board</code> 代表糖果所在的方格，不同的正整数 <code>board[i][j]</code> 代表不同种类的糖果，如果 <code>board[i][j] == 0</code> 代表&nbsp;<code>(i, j)</code> 这个位置是空的。</p>\n",
    "\n",
    "<p>给定的方格是玩家移动后的游戏状态，现在需要你根据以下规则粉碎糖果，使得整个方格处于稳定状态并最终输出：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果有三个及以上水平或者垂直相连的同种糖果，同一时间将它们粉碎，即将这些位置变成空的。</li>\n",
    "\t<li>在同时粉碎掉这些糖果之后，如果有一个空的位置上方还有糖果，那么上方的糖果就会下落直到碰到下方的糖果或者底部，这些糖果都是同时下落，也不会有新的糖果从顶部出现并落下来。</li>\n",
    "\t<li>通过前两步的操作，可能又会出现可以粉碎的糖果，请继续重复前面的操作。</li>\n",
    "\t<li>当不存在可以粉碎的糖果，也就是状态稳定之后，请输出最终的状态。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要模拟上述规则并使整个方格达到稳定状态，并输出。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 :</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/candy_crush_example_2.png\" style=\"height: 411px; width: 600px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]\n",
    "<strong>输出: </strong>[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> board = [[1,3,5,5,2],[3,4,3,3,1],[3,2,4,5,2],[2,4,4,5,5],[1,4,4,1,1]]\n",
    "<strong>输出:</strong> [[1,3,0,0,0],[3,4,0,5,2],[3,2,0,3,1],[2,4,0,5,2],[1,4,3,1,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == board.length</code></li>\n",
    "\t<li><code>n == board[i].length</code></li>\n",
    "\t<li><code>3 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= board[i][j] &lt;= 2000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [candy-crush](https://leetcode.cn/problems/candy-crush/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [candy-crush](https://leetcode.cn/problems/candy-crush/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]', '[[1,3,5,5,2],[3,4,3,3,1],[3,2,4,5,2],[2,4,4,5,5],[1,4,4,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        res: List[int] = []\n",
    "        i: int = 0\n",
    "        j: int = 0\n",
    "        pick: int = 0\n",
    "            \n",
    "        while i < len(a) and j < len(b):\n",
    "            if a[i] < b[j]:\n",
    "                pick = a[i]\n",
    "                i += 1\n",
    "            elif b[j] < a[i]:\n",
    "                pick = b[j]\n",
    "                j += 1\n",
    "            else:  # a[i] == b[j]\n",
    "                pick = a[i]\n",
    "                i, j = i + 1, j + 1\n",
    "            res.append(pick)\n",
    "            \n",
    "        while i < len(a):\n",
    "            res.append(a[i])\n",
    "            i += 1\n",
    "        while j < len(b):\n",
    "            res.append(b[j])\n",
    "            j += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "    def crush(self, board: List[List[int]]) -> bool:\n",
    "        crushed: bool = False\n",
    "        pat_begin: int = 0\n",
    "        pat_end: int = 0\n",
    "\n",
    "        del_col1: List[List[int]] = [[] for _ in range(len(board[0]))]\n",
    "        for r in range(len(board)):\n",
    "            pat_begin = 0\n",
    "\n",
    "            while pat_begin < len(board[r]) - 2:\n",
    "                if board[r][pat_begin] == 0:\n",
    "                    pat_begin += 1\n",
    "                    continue\n",
    "\n",
    "                pat_end = pat_begin + 1\n",
    "                while (\n",
    "                    pat_end < len(board[r])\n",
    "                    and board[r][pat_end] == board[r][pat_begin]\n",
    "                ):\n",
    "                    pat_end += 1\n",
    "\n",
    "                if pat_end - pat_begin >= 3:\n",
    "                    for c in range(pat_begin, pat_end):\n",
    "                        del_col1[c].append(r)\n",
    "\n",
    "                pat_begin = pat_end\n",
    "                \n",
    "        del_col2: List[List[int]] = [[] for _ in range(len(board[0]))]\n",
    "        for c in range(len(board[0])):\n",
    "            pat_begin = 0\n",
    "            \n",
    "            while pat_begin < len(board) - 2:\n",
    "                if board[pat_begin][c] == 0:\n",
    "                    pat_begin += 1\n",
    "                    continue\n",
    "\n",
    "                pat_end = pat_begin + 1\n",
    "                while (\n",
    "                    pat_end < len(board)\n",
    "                    and board[pat_end][c] == board[pat_begin][c]\n",
    "                ):\n",
    "                    pat_end += 1\n",
    "\n",
    "                if pat_end - pat_begin >= 3:\n",
    "                    for r in range(pat_begin, pat_end):\n",
    "                        del_col2[c].append(r)\n",
    "\n",
    "                pat_begin = pat_end\n",
    "\n",
    "        w: int = 0\n",
    "        r: int = 0\n",
    "        to_del: List[int] = []\n",
    "\n",
    "        for c in range(len(board[0])):\n",
    "            to_del = self.merge(del_col1[c], del_col2[c])\n",
    "            if len(to_del) == 0:\n",
    "                continue\n",
    "\n",
    "            crushed = True\n",
    "            w, r = to_del[-1], to_del[-1]\n",
    "            while len(to_del) > 0:\n",
    "                if r == to_del[-1]:\n",
    "                    to_del.pop()\n",
    "                else:\n",
    "                    board[w][c] = board[r][c]\n",
    "                    w -= 1\n",
    "                r -= 1\n",
    "            while r >= 0:\n",
    "                board[w][c] = board[r][c]\n",
    "                r, w = r - 1, w - 1\n",
    "            while w >= 0:\n",
    "                board[w][c] = 0\n",
    "                w -= 1\n",
    "\n",
    "        return crushed\n",
    "\n",
    "\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        while self.crush(board):\n",
    "            pass\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        f=0\n",
    "        while True:\n",
    "            f=0\n",
    "            for x in range(m):\n",
    "                for y in range(n-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x][y+1])==abs(board[x][y+2]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x][y+1]=-tmp\n",
    "                        board[x][y+2]=-tmp\n",
    "\n",
    "            for y in range(n):\n",
    "                for x in range(m-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x+1][y])==abs(board[x+2][y]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x+1][y]=-tmp\n",
    "                        board[x+2][y]=-tmp\n",
    "\n",
    "            if f==1:\n",
    "                for y in range(n):\n",
    "                    rr=m-1\n",
    "                    for x in range(m-1,-1,-1):\n",
    "                        if board[x][y]>=0:\n",
    "                            board[rr][y]=board[x][y]\n",
    "                            rr=rr-1\n",
    "                    while rr>=0:\n",
    "                        board[rr][y]=0\n",
    "                        rr-=1\n",
    "\n",
    "            if f==0:\n",
    "                break\n",
    "        return board\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row,column = len(board),len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(row):\n",
    "            for c in range(column-2):\n",
    "                if abs(board[r][c])==abs(board[r][c+1])==abs(board[r][c+2])!=0:\n",
    "                    board[r][c]=board[r][c+1]=board[r][c+2]=-abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(column):\n",
    "            for r in range(row-2):\n",
    "                if abs(board[r][c])==abs(board[r+1][c])==abs(board[r+2][c])!=0:\n",
    "                    board[r][c]=board[r+1][c]=board[r+2][c]=-abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(column):\n",
    "            wr = row-1\n",
    "            for r in range(row-1,-1,-1):\n",
    "                if board[r][c]>0: \n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr-=1\n",
    "            for wr in range(wr,-1,-1):\n",
    "                board[wr][c] = 0\n",
    "        \n",
    "        return self.candyCrush(board) if todo else board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def check():\n",
    "            state = [[0] * n for _ in range(m)]\n",
    "            signal = 0\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n - 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur != 0 and cur == board[i][j + 1] and cur == board[i][j + 2]:\n",
    "                        signal = 1\n",
    "                        state[i][j:j+3] = [1]*3\n",
    "                        j += 2\n",
    "                        while j + 1 < n and board[i][j + 1] == board[i][j]:\n",
    "                            state[i][j + 1] = 1\n",
    "                            j += 1\n",
    "                    j += 1\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                while i >= 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur == 0:\n",
    "                        break\n",
    "                    if cur == board[i - 1][j] and cur == board[i - 2][j]:\n",
    "                        signal = 1\n",
    "                        for x in range(i, i - 3, -1):\n",
    "                            state[x][j] = 1\n",
    "                        i -= 2\n",
    "                        while i >= 1 and board[i - 1][j] == board[i][j]:\n",
    "                            state[i - 1][j] = 1\n",
    "                            i -= 1\n",
    "                    i -= 1\n",
    "            return state, signal\n",
    "        \n",
    "        def revise(state):\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                pos = m - 1\n",
    "                while pos >= 0:\n",
    "                    if state[pos][j] != 1:\n",
    "                        board[i][j] = board[pos][j]\n",
    "                        i -= 1\n",
    "                    pos -= 1\n",
    "                while i >= 0 and board[i][j] != 0:\n",
    "                    board[i][j] = 0\n",
    "                    i -= 1\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            sta, sig = check()\n",
    "            if sig == 0:\n",
    "                return board\n",
    "            revise(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Repeatedly until the board is stable:\n",
    "        Find the candies to crush:\n",
    "            Iterate through the board and for each cell, check if it starts a row or column of 3 candies of the same type.\n",
    "            Mark the candies to crush in-place by setting their value to negative.\n",
    "        Crush and drop the candies:\n",
    "            Iterate through the board by ascending column and descending row.\n",
    "            Keep track of the number of empty cells in the current column and drop the candies above by that number.\n",
    "    Time complexity: O(mn * mn) (loose upper bound). Space complexity: O(1).\n",
    "    '''\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            stable = True\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if i + 2 < m and abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i + 1][j] = board[i + 2][j] = -abs(board[i][j])\n",
    "                    if j + 2 < n and abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i][j + 1] = board[i][j + 2] = -abs(board[i][j])\n",
    "            \n",
    "            if stable:\n",
    "                return board\n",
    "                \n",
    "            for j in range(n):\n",
    "                numEmpty = 0\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] <= 0:\n",
    "                        board[i][j] = 0\n",
    "                        numEmpty += 1\n",
    "                    else:\n",
    "                        board[i][j], board[i+numEmpty][j] = board[i+numEmpty][j], board[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        def bfs(i, j):\n",
    "            v = board[i][j]\n",
    "            visited = set()\n",
    "            # Test row\n",
    "            row_candies = []\n",
    "            x = i\n",
    "            while x < m and board[x][j] == v:\n",
    "                row_candies.append((x, j))\n",
    "                x += 1\n",
    "            if len(row_candies) >= 3:\n",
    "                visited.update(row_candies)\n",
    "            # Test column\n",
    "            column_candies = []\n",
    "            y = j\n",
    "            while y < n and board[i][y] == v:\n",
    "                column_candies.append((i, y))\n",
    "                y += 1\n",
    "            if len(column_candies) >= 3:\n",
    "                visited.update(column_candies)\n",
    "            return visited\n",
    "\n",
    "        while True:\n",
    "            # Judge what grids will be crushed\n",
    "            drop = [[0] * n for _ in range(m)]\n",
    "            should_drop = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    visited = bfs(i, j)\n",
    "                    if len(visited) >= 3:\n",
    "                        for x, y in visited:\n",
    "                            drop[x][y] = 1\n",
    "                            should_drop = True\n",
    "            if not should_drop:\n",
    "                return board\n",
    "\n",
    "            # Crush and drop each column\n",
    "            for j in range(n):\n",
    "                bottom = m - 1\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    if drop[i][j] == 1:\n",
    "                        continue\n",
    "                    board[bottom][j] = board[i][j]\n",
    "                    bottom -= 1\n",
    "                while bottom != -1:\n",
    "                    board[bottom][j] = 0\n",
    "                    bottom -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "#         def in_board(i, j):\n",
    "#             if i < len(board) and i >= 0 and j < len(board[0]) and j >= 0:\n",
    "#                 return True\n",
    "#             return False\n",
    "        \n",
    "#         def check_adjacent(board, i, j):\n",
    "#             dirs = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "#             cur_val = board[i][j]\n",
    "#             board[i][j] = 0\n",
    "#             temp_list = []\n",
    "#             for dir in dirs:\n",
    "#                 cur_i = i + dir[0]\n",
    "#                 cur_j = j + dir[1]\n",
    "#                 if in_board(cur_i, cur_j) and board[cur_i][cur_j] == cur_val:\n",
    "#                     temp_list = temp_list + check_adjacent(board, cur_i, cur_j)\n",
    "#             temp_list.append((i, j))\n",
    "#             return temp_list\n",
    "        \n",
    "#         def drop_board(): # todo update algorithm if possible\n",
    "#             for j in range(len(board[0])-1, -1, -1):\n",
    "#                 for i in range(len(board)-1, -1, -1):\n",
    "#                     if board[i][j] == 0:\n",
    "#                         board[0][j] = 0\n",
    "#                         for k in range(1, i + 1):\n",
    "#                             board[k][j] = board[k-1][j]\n",
    "#         def print_board():\n",
    "#             for i in range(len(board)):\n",
    "#                 for j in range(len(board[0])):\n",
    "#                     print(board[i][j], end=\" \")\n",
    "#                 print(\"\")\n",
    "\n",
    "        \n",
    "#         while True:\n",
    "#             prev_board = copy.deepcopy(board)\n",
    "#             # check\n",
    "#             for i in range(len(board)):\n",
    "#                 for j in range(len(board[0])):\n",
    "#                     if board[i][j] != 0:\n",
    "#                         temp_list = check_adjacent(board[:][:], i, j)\n",
    "#                         print(f\"temp_list : {temp_list}\")\n",
    "#                         if len(temp_list) >= 3:\n",
    "#                             for loc in temp_list:\n",
    "#                                 board[loc[0]][loc[1]] = 0\n",
    "#             print(\"board before dropping\")\n",
    "#             print_board()\n",
    "#             # drop\n",
    "#             drop_board()\n",
    "#             print(\"board after dropping\")\n",
    "#             print_board()\n",
    "\n",
    "#             if prev_board == board:\n",
    "#                 break\n",
    "#         return board\n",
    "        \n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        while need_todo:\n",
    "            need_todo = False\n",
    "            for r in range(row):\n",
    "                for c in range(col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs (board[r][c+2]):\n",
    "                        need_todo = True \n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c] = tmp \n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp \n",
    "            for c in range(col):\n",
    "                for r in range(row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True \n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c] = tmp \n",
    "                        board[r+1][c] = tmp \n",
    "                        board[r+2][c] = tmp \n",
    "            if need_todo == True:\n",
    "                for c in range(col):\n",
    "                    rr = row - 1\n",
    "                    for r in range(row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        Row, Col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        ################ 注意L形也是可以的\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\n",
    "            need_todo = False\n",
    "            #### 先搞定行\n",
    "            for r in range(Row):\n",
    "                for c in range(Col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\n",
    "                        need_todo = True\n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp\n",
    "            #### 再搞定列\n",
    "            for c in range(Col):\n",
    "                for r in range(Row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True\n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r+1][c] = tmp\n",
    "                        board[r+2][c] = tmp\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\n",
    "            if need_todo == True:\n",
    "                for c in range(Col):\n",
    "                    rr = Row - 1\n",
    "                    for r in range(Row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m,n,mark=len(board),len(board[0]),True\n",
    "        while mark:\n",
    "            mark=False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j]==0:\n",
    "                        continue\n",
    "                    if j<n-2 and abs(board[i][j])==abs(board[i][j+1])==abs(board[i][j+2]):\n",
    "                        val=-abs(board[i][j])\n",
    "                        board[i][j]=val\n",
    "                        board[i][j+1]=val\n",
    "                        board[i][j+2]=val\n",
    "                        mark=True\n",
    "                    if i<m-2 and abs(board[i][j])==abs(board[i+1][j])==abs(board[i+2][j]):\n",
    "                        mark=True\n",
    "                        val=-abs(board[i][j])\n",
    "                        board[i][j]=val\n",
    "                        board[i+1][j]=val\n",
    "                        board[i+2][j]=val\n",
    "                        mark=True\n",
    "            for j in range(n):\n",
    "                cursor=m-1\n",
    "                for i in range(m-1,-1,-1):\n",
    "                    if board[i][j]>0:\n",
    "                        board[cursor][j]=board[i][j]\n",
    "                        cursor-=1\n",
    "                for i in range(cursor,-1,-1):\n",
    "                    board[i][j]=0\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C - 2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(board),len(board[0])\n",
    "        xiao=set()\n",
    "        def bl():\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isKill(i,j):\n",
    "                        xiao.add((i,j))\n",
    "            if len(xiao)==0:\n",
    "                return False\n",
    "            return True\n",
    "        def isKill(i,j):\n",
    "            t=board[i][j]\n",
    "            if t==0:\n",
    "                return False\n",
    "            if i+2<m and board[i+1][j]==t and board[i+2][j]==t:\n",
    "                return True\n",
    "            if i+1<m and i-1>=0 and board[i-1][j]==t and board[i+1][j]==t:\n",
    "                return True\n",
    "            if i-2>=0 and board[i-2][j]==t and board[i-1][j]==t:\n",
    "                return True\n",
    "            if j+2<n and board[i][j+2]==t and board[i][j+1]==t:\n",
    "                return True\n",
    "            if j+1<n and j-1>=0 and board[i][j+1]==t and board[i][j-1]==t:\n",
    "                return True\n",
    "            if j-2>=0 and board[i][j-2]==t and board[i][j-1]==t:\n",
    "                return True\n",
    "            return False\n",
    "        def xxc(i,j):\n",
    "            for t in range(i,-1,-1):\n",
    "                if t==0:\n",
    "                    board[t][j]=0\n",
    "                else:\n",
    "                    board[t][j]=board[t-1][j]\n",
    "        def xc():\n",
    "            ltxiao=list(xiao)\n",
    "            ltxiao=sorted(ltxiao,key= lambda k:k[0],reverse=False)\n",
    "            # print(ltxiao)\n",
    "            for i,j in ltxiao:\n",
    "                xxc(i,j)\n",
    "        while(bl()):\n",
    "            xc()\n",
    "            xiao=set()\n",
    "        # for i in board:\n",
    "        #     print(i)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        return self.answer_1(board)\n",
    "\n",
    "    def answer_1(self, board):\n",
    "        row_len = len(board)\n",
    "        col_len = len(board[0])\n",
    "\n",
    "        to_do = False\n",
    "\n",
    "        # 标记\n",
    "        for row_index in range(row_len):\n",
    "            for col_index in range(col_len - 2):\n",
    "                current_num = abs(board[row_index][col_index])\n",
    "                second_num = abs(board[row_index][col_index + 1])\n",
    "                third_num = abs(board[row_index][col_index + 2])\n",
    "\n",
    "                if not (current_num == second_num == third_num and current_num != 0):\n",
    "                    continue\n",
    "\n",
    "                to_do = True\n",
    "\n",
    "                board[row_index][col_index] = -current_num\n",
    "                board[row_index][col_index + 1] = -current_num\n",
    "                board[row_index][col_index + 2] = -current_num\n",
    "\n",
    "        for row_index in range(row_len - 2):\n",
    "            for col_index in range(col_len):\n",
    "                current_num = abs(board[row_index][col_index])\n",
    "                second_num = abs(board[row_index + 1][col_index])\n",
    "                third_num = abs(board[row_index + 2][col_index])\n",
    "\n",
    "                if not (current_num == second_num == third_num and current_num != 0):\n",
    "                    continue\n",
    "\n",
    "                to_do = True\n",
    "\n",
    "                board[row_index][col_index] = -current_num\n",
    "                board[row_index + 1][col_index] = -current_num\n",
    "                board[row_index + 2][col_index] = -current_num\n",
    "\n",
    "        # 清除\n",
    "        for col_index in range(col_len):\n",
    "            tmp_row_index = row_len - 1\n",
    "            for row_index in range(row_len - 1, -1, -1):\n",
    "                if board[row_index][col_index] > 0:\n",
    "                    board[tmp_row_index][col_index] = board[row_index][col_index]\n",
    "                    tmp_row_index -= 1\n",
    "\n",
    "            for row_index in range(tmp_row_index , -1, -1):\n",
    "                board[row_index][col_index] = 0\n",
    "        return self.answer_1(board) if to_do else board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        f=0\n",
    "        while True:\n",
    "            f=0\n",
    "            for x in range(m):\n",
    "                for y in range(n-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x][y+1])==abs(board[x][y+2]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x][y+1]=-tmp\n",
    "                        board[x][y+2]=-tmp\n",
    "\n",
    "            for y in range(n):\n",
    "                for x in range(m-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x+1][y])==abs(board[x+2][y]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x+1][y]=-tmp\n",
    "                        board[x+2][y]=-tmp\n",
    "\n",
    "            if f==1:\n",
    "                for y in range(n):\n",
    "                    rr=m-1\n",
    "                    for x in range(m-1,-1,-1):\n",
    "                        if board[x][y]>0:\n",
    "                            board[rr][y]=board[x][y]\n",
    "                            rr=rr-1\n",
    "                    while rr>=0:\n",
    "                        board[rr][y]=0\n",
    "                        rr-=1\n",
    "\n",
    "            if f==0:\n",
    "                break\n",
    "        return board\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board):\n",
    "        # 消除过程分为两步，一是将可消除部分置为零，二是将空位上方的部分落下\n",
    "        m, n = len(board), len(board[0])\n",
    "        mem = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def crush():\n",
    "            flg, flg1 = 0, 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    x0, y0 = 0, 0\n",
    "                    for x in range(i + 1, m):\n",
    "                        if board[i][j] != 0 and board[x][j] == board[i][j]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            if board[i][j] == 0 or x - i <= 2:\n",
    "                                pass\n",
    "                            else:\n",
    "                                for t in range(i, x):\n",
    "                                    mem[t][j] = 1\n",
    "                                flg = 1\n",
    "                                x0 = 1\n",
    "                            break\n",
    "                    else:\n",
    "                        if board[i][j] != 0 and m - i > 2 and x0 != 1:\n",
    "                            for t in range(i, m):\n",
    "                                mem[t][j] = 1\n",
    "                            flg = 1\n",
    "                    for y in range(j + 1, n):\n",
    "                        if board[i][j] != 0 and board[i][y] == board[i][j]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            if board[i][j] == 0 or y - j <= 2:\n",
    "                                pass\n",
    "                            else:\n",
    "                                for t in range(j, y):\n",
    "                                    mem[i][t] = 1\n",
    "                                flg1 = 1\n",
    "                                y0 = 1\n",
    "                            break\n",
    "                    else:\n",
    "                        if board[i][j] != 0 and n - j > 2 and y0 != 1:\n",
    "                            for t in range(j, n):\n",
    "                                mem[i][t] = 1\n",
    "                            flg1 = 1\n",
    "            if flg == 1 or flg1 == 1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def fall():\n",
    "            for j in range(n):\n",
    "                # for i in range(m - 2, -1, -1):\n",
    "                #     if mem[i + 1][j] == 1:\n",
    "                #         mem[i + 1][j] = 0\n",
    "                #         mem[i][j] = 1\n",
    "                #         board[i + 1][j] = board[i][j]\n",
    "                #         board[i][j] = 0\n",
    "                # 首先找到底，即最底的1，然后找到下落点，即最底的0，将下落点置为1，将底置为0；底往上走\n",
    "                i1, i2 = m - 1, m - 1\n",
    "                while i1 >= 0:\n",
    "                    if mem[i1][j] == 1:\n",
    "                        i2 = i1 - 1\n",
    "                        while i2 >= 0 and mem[i2][j] != 0:\n",
    "                            i2 -= 1\n",
    "                        if i2 < 0:\n",
    "                            board[i1][j] = 0\n",
    "                        else:\n",
    "                            board[i1][j] = board[i2][j]\n",
    "                            board[i2][j] = 0\n",
    "                            mem[i1][j] = 0\n",
    "                            mem[i2][j] = 1\n",
    "                    i1 -= 1\n",
    "\n",
    "        i = 0\n",
    "        while crush() and i < 50:\n",
    "            fall()\n",
    "            i += 1\n",
    "        return board\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "\n",
    "        remove = [[False] * m for _ in range(n)]\n",
    "        todo = True\n",
    "        # first mark the elements to be eliminated horizontally\n",
    "        while todo:\n",
    "            todo = False\n",
    "            for r in range(n):\n",
    "                left = 0\n",
    "                right = 0\n",
    "                while left < m:\n",
    "                    while right < m and board[r][left] == board[r][right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right - left >= 3 and board[r][left] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(left, right):\n",
    "                            remove[r][idx] = True\n",
    "                    left = right\n",
    "    \n",
    "            # second mark the elements to be eliminated vertically\n",
    "            for c in range(m):\n",
    "                up = 0\n",
    "                down = 0\n",
    "                while up < n:\n",
    "                    while down < n and board[up][c] == board[down][c]:\n",
    "                        down += 1\n",
    "                    \n",
    "                    if down - up >= 3 and board[up][c] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(up, down):\n",
    "                            remove[idx][c] = True\n",
    "                    up = down\n",
    "            \n",
    "            # vertically squash every removed element row by row from bottom to top\n",
    "            for r in range(n - 1, -1, -1):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        index = r\n",
    "                        while index >= 0 and remove[index][c] and board[index][c] != 0:\n",
    "                            index -= 1\n",
    "                        if index >= 0:\n",
    "                            board[r][c] = board[index][c]\n",
    "                            remove[r][c] = False\n",
    "                            remove[index][c] = True\n",
    "            \n",
    "            for r in range(n):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        board[r][c] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        def check(board_):\n",
    "            # 检查是存在能够消除的格子并标记\n",
    "            flags = [[0]*n for _ in range(m)]\n",
    "            f = False\n",
    "            # 先检查行\n",
    "            for i in range(m):\n",
    "                for j in range(n-2):\n",
    "                    if board_[i][j]==board_[i][j+1]==board_[i][j+2]!=0:\n",
    "                        flags[i][j]=1\n",
    "                        flags[i][j+1]=1\n",
    "                        flags[i][j+2]=1\n",
    "                        f = True\n",
    "            # 检查列\n",
    "            for j in range(n):\n",
    "                for i in range(m-2):\n",
    "                    if board_[i][j]==board_[i+1][j]==board_[i+2][j]!=0:\n",
    "                        flags[i][j]=1\n",
    "                        flags[i+1][j]=1\n",
    "                        flags[i+2][j]=1\n",
    "                        f = True\n",
    "            return f, flags\n",
    "        \n",
    "        def ruin(board_, flags):\n",
    "            for j in range(n):\n",
    "                # 按列写回糖果\n",
    "                read = m-1\n",
    "                write = m-1\n",
    "                while write>=0:\n",
    "                    while read >= 0 and flags[read][j]==1:\n",
    "                        read -= 1\n",
    "                    \n",
    "                    if read < 0:\n",
    "                        board_[write][j] = 0\n",
    "                    else:\n",
    "                        board_[write][j] = board_[read][j]\n",
    "                    write -= 1\n",
    "                    read -= 1\n",
    "            return board_\n",
    "\n",
    "        while True:\n",
    "            f, flag = check(board)\n",
    "            if f:\n",
    "                board = ruin(board, flag)\n",
    "            else:\n",
    "                return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        def update():\n",
    "            stable = True\n",
    "\n",
    "            # 获取待粉碎的糖果\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n:\n",
    "                    if board[i][j] == 0:\n",
    "                        j += 1\n",
    "                        continue\n",
    "                    v = abs(board[i][j])\n",
    "                    k = j + 1\n",
    "                    while k < n and abs(board[i][k]) == v:\n",
    "                        k += 1\n",
    "                    if k - j >= 3:\n",
    "                        stable = False\n",
    "                        for jj in range(j, k):\n",
    "                            board[i][jj] = -v\n",
    "                    j = k\n",
    "            for j in range(n):\n",
    "                i = 0\n",
    "                while i < m:\n",
    "                    if board[i][j] == 0:\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    v = abs(board[i][j])\n",
    "                    k = i + 1\n",
    "                    while k < m and abs(board[k][j]) == v:\n",
    "                        k += 1\n",
    "                    if k - i >= 3:\n",
    "                        stable = False\n",
    "                        for ii in range(i, k):\n",
    "                            board[ii][j] = -v\n",
    "                    i = k\n",
    "            \n",
    "            if stable:\n",
    "                return\n",
    "\n",
    "            # 更新\n",
    "            for j in range(n):\n",
    "                i0 = i1 = m - 1\n",
    "                while i1 >= 0:\n",
    "                    if board[i1][j] < 0:\n",
    "                        i1 -= 1\n",
    "                        continue\n",
    "                    board[i0][j] = board[i1][j]\n",
    "                    i0 -= 1\n",
    "                    i1 -= 1\n",
    "                for i1 in range(i0, -1, -1):\n",
    "                    board[i1][j] = 0\n",
    "            \n",
    "            update()\n",
    "        \n",
    "        update()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        while True:\n",
    "            marked=self.mark(board)\n",
    "            # 没办法碾碎糖果,并且没有值为负数\n",
    "            if not marked:\n",
    "                return board\n",
    "            else: self.crush(board)\n",
    "            \n",
    "    \n",
    "    def mark(self,board:List[List[int]])->bool:\n",
    "        marked=False\n",
    "        m,n=len(board),len(board[0])\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if c>=1 and c<n-1 and abs(board[r][c])==abs(board[r][c-1])==abs(board[r][c+1]) and abs(board[r][c])!=0:\n",
    "                    board[r][c]=board[r][c-1]=board[r][c+1]=-abs(board[r][c])\n",
    "                    marked=True\n",
    "        for c in range(n):\n",
    "            for r in range(m):\n",
    "                if r>=1 and r<m-1 and abs(board[r][c])==abs(board[r-1][c])==abs(board[r+1][c]) and abs(board[r][c])!=0:\n",
    "                    board[r][c]=board[r-1][c]=board[r+1][c]=-abs(board[r][c])\n",
    "                    marked=True\n",
    "        return marked\n",
    "\n",
    "    def crush(self,board:List[List[int]]):\n",
    "        m,n=len(board),len(board[0])\n",
    "        for c in range(n):\n",
    "            cur_r=m-1\n",
    "            for r in range(m-1,-1,-1):\n",
    "                if board[r][c]>0:\n",
    "                    board[cur_r][c]=board[r][c]\n",
    "                    cur_r-=1\n",
    "            while cur_r>=0:\n",
    "                board[cur_r][c]=0\n",
    "                cur_r-=1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        # def crush():\n",
    "        #     to_crush = set()\n",
    "        #     # 行\n",
    "        #     for i in range(m):\n",
    "        #         j1, j2 = 0, 0\n",
    "        #         while j2 <= n:\n",
    "        #             if j2 == n or board[i][j2] != board[i][j1]:\n",
    "        #                 if j2 - j1 >= 3 and board[i][j1] > 0:\n",
    "        #                     for k in range(j1, j2):\n",
    "        #                         to_crush.add((i, k))\n",
    "        #                 j1 = j2\n",
    "        #             j2 += 1\n",
    "        #     # 列\n",
    "        #     for j in range(n):\n",
    "        #         i1, i2 = 0, 0\n",
    "        #         while i2 <= m:\n",
    "        #             if i2 == m or board[i1][j] != board[i2][j]:\n",
    "        #                 if i2 - i1 >= 3 and board[i1][j] > 0:\n",
    "        #                     for k in range(i1, i2):\n",
    "        #                         to_crush.add((k, j))\n",
    "        #                 i1 = i2\n",
    "        #             i2 += 1\n",
    "        #     for i, j in to_crush:\n",
    "        #         board[i][j] = 0\n",
    "        #     return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        label = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n - 2):\n",
    "                if abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2]) != 0:\n",
    "                    board[i][j] = board[i][j+1] = board[i][j+2] = -abs(board[i][j])\n",
    "                    label = 1\n",
    "        for j in range(n):\n",
    "            for i in range(m - 2):\n",
    "                if abs(board[i][j]) == abs(board[i+1][j]) == abs(board[i+2][j]) != 0:\n",
    "                    board[i][j] = board[i+1][j] = board[i+2][j] = -abs(board[i][j])\n",
    "                    label = 1     \n",
    "        for j in range(n):\n",
    "            wr = m-1\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if board[i][j] > 0:\n",
    "                    board[wr][j] = board[i][j]\n",
    "                    wr -= 1\n",
    "            for i in range(wr, -1, -1):\n",
    "                board[i][j] = 0\n",
    "        if label:\n",
    "            return self.candyCrush(board)\n",
    "        else:\n",
    "            return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        stable = None\n",
    "        while not stable:\n",
    "            stable = True\n",
    "            # check column axis lines\n",
    "            for r in range(row):\n",
    "                for c in range(col-2):\n",
    "                    if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                        board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                        stable = False\n",
    "            # check row axis lines\n",
    "            for r in range(row-2):\n",
    "                for c in range(col):\n",
    "                    if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                        board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                        stable = False\n",
    "            # for each column, from bottom to top eliminate the negative values\n",
    "            for c in range(col):\n",
    "                row_ptr = row - 1\n",
    "                for r in range(row-1, -1, -1):\n",
    "                    if board[r][c] > 0:\n",
    "                        board[row_ptr][c] = board[r][c]\n",
    "                        row_ptr -= 1\n",
    "                for remain in range(row_ptr, -1, -1):\n",
    "                    board[remain][c] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def check():\n",
    "            signal = 0\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n - 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur != 0 and cur == board[i][j + 1] and cur == board[i][j + 2]:\n",
    "                        signal = 1\n",
    "                        state[i][j:j+3] = [1]*3\n",
    "                        j += 2\n",
    "                        while j + 1 < n and board[i][j + 1] == board[i][j]:\n",
    "                            state[i][j + 1] = 1\n",
    "                            j += 1\n",
    "                    j += 1\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                while i >= 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur == 0:\n",
    "                        break\n",
    "                    if cur == board[i - 1][j] and cur == board[i - 2][j]:\n",
    "                        signal = 1\n",
    "                        for x in range(i, i - 3, -1):\n",
    "                            state[x][j] = 1\n",
    "                        i -= 2\n",
    "                        while i >= 1 and board[i - 1][j] == board[i][j]:\n",
    "                            state[i - 1][j] = 1\n",
    "                            i -= 1\n",
    "                    i -= 1\n",
    "            return state, signal\n",
    "        \n",
    "        def revise(state):\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                pos = m - 1\n",
    "                while pos >= 0:\n",
    "                    if state[pos][j] != 1:\n",
    "                        board[i][j] = board[pos][j]\n",
    "                        i -= 1\n",
    "                    state[pos][j] = 0\n",
    "                    pos -= 1\n",
    "                while i >= 0 and board[i][j] != 0:\n",
    "                    board[i][j] = 0\n",
    "                    i -= 1\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        state = [[0] * n for _ in range(m)]\n",
    "        while True:\n",
    "            sta, sig = check()\n",
    "            if sig == 0:\n",
    "                return board\n",
    "            revise(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        Row, Col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        ################ 注意L形也是可以的\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\n",
    "            need_todo = False\n",
    "            #### 先搞定行\n",
    "            for r in range(Row):\n",
    "                for c in range(Col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\n",
    "                        need_todo = True\n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp\n",
    "            #### 再搞定列\n",
    "            for c in range(Col):\n",
    "                for r in range(Row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True\n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r+1][c] = tmp\n",
    "                        board[r+2][c] = tmp\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\n",
    "            if need_todo == True:\n",
    "                for c in range(Col):\n",
    "                    rr = Row - 1\n",
    "                    for r in range(Row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "     def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Repeatedly until the board is stable:\n",
    "        Find the candies to crush:\n",
    "            Iterate through the board and for each cell, check if it starts a row or column of 3 candies of the same type.\n",
    "            Mark the candies to crush in-place by setting their value to negative.\n",
    "        Crush and drop the candies:\n",
    "            Iterate through the board by ascending column and descending row.\n",
    "            Keep track of the number of empty cells in the current column and drop the candies above by that number.\n",
    "    Time complexity: O(mn * mn) (loose upper bound). Space complexity: O(1).\n",
    "    '''\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            stable = True\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if i + 2 < m and abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i + 1][j] = board[i + 2][j] = -abs(board[i][j])\n",
    "                    if j + 2 < n and abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i][j + 1] = board[i][j + 2] = -abs(board[i][j])\n",
    "            \n",
    "            if stable:\n",
    "                break\n",
    "                \n",
    "            for j in range(n):\n",
    "                numEmpty = 0\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] <= 0:\n",
    "                        board[i][j] = 0\n",
    "                        numEmpty += 1\n",
    "                    else:\n",
    "                        board[i][j], board[i+numEmpty][j] = board[i+numEmpty][j], board[i][j]\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            rowset, colset, locset = set(), set(), set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] != 0:\n",
    "                        if i * 100 + j not in rowset:\n",
    "                            j2 = j\n",
    "                            while j2 < n and board[i][j2] == board[i][j]:\n",
    "                                j2 += 1\n",
    "                            if j2 - j > 2:\n",
    "                                for x in range(j, j2):\n",
    "                                    loc = i * 100 + x\n",
    "                                    locset.add(loc)\n",
    "                                    rowset.add(loc)\n",
    "                        if i * 100 + j not in colset:\n",
    "                            i2 = i\n",
    "                            while i2 < m and board[i2][j] == board[i][j]:\n",
    "                                i2 += 1\n",
    "                            if i2 - i > 2:\n",
    "                                for x in range(i, i2):\n",
    "                                    loc = x * 100 + j\n",
    "                                    locset.add(loc)\n",
    "                                    colset.add(loc)\n",
    "            if len(locset) == 0:\n",
    "                return board\n",
    "            for loc in locset:\n",
    "                board[loc // 100][loc % 100] = 0\n",
    "            for j in range(n):\n",
    "                zeroi = m - 1\n",
    "                while zeroi > -1 and board[zeroi][j] != 0:\n",
    "                    zeroi -= 1\n",
    "                for i in range(zeroi - 1, -1, -1):\n",
    "                    if board[i][j] != 0:\n",
    "                        board[zeroi][j] = board[i][j]\n",
    "                        board[i][j] = 0\n",
    "                        zeroi -= 1\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        def crush():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i >= 2 and abs(board[i-2][j]) == abs(board[i-1][j]) == abs(board[i][j]) != 0:\n",
    "                        c = abs(board[i][j])\n",
    "                        board[i-2][j] = board[i-1][j] = board[i][j] = - c\n",
    "                        cnt += 1\n",
    "                    if j >= 2 and abs(board[i][j-2]) == abs(board[i][j-1]) == abs(board[i][j]) != 0:\n",
    "                        c = abs(board[i][j])\n",
    "                        board[i][j-2] = board[i][j-1] = board[i][j] = - c\n",
    "                        cnt += 1\n",
    "            return cnt \n",
    "        def check():\n",
    "            for j in range(n):\n",
    "                to_fill = m-1\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] > 0:\n",
    "                        tmp = board[i][j]\n",
    "                        board[i][j] = 0\n",
    "                        board[to_fill][j] = abs(tmp)\n",
    "                        to_fill -= 1\n",
    "                    else:\n",
    "                        board[i][j] = 0\n",
    "\n",
    "        # i = 0\n",
    "        while True:\n",
    "            c = crush()\n",
    "            # print(c)\n",
    "            if c == 0:\n",
    "                return board\n",
    "            check()\n",
    "            # i += 1\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        Row, Col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        ################ 注意L形也是可以的\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\n",
    "            need_todo = False\n",
    "            #### 先搞定行\n",
    "            for r in range(Row):\n",
    "                for c in range(Col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\n",
    "                        need_todo = True\n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp\n",
    "            #### 再搞定列\n",
    "            for c in range(Col):\n",
    "                for r in range(Row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True\n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r+1][c] = tmp\n",
    "                        board[r+2][c] = tmp\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\n",
    "            if need_todo == True:\n",
    "                for c in range(Col):\n",
    "                    rr = Row - 1\n",
    "                    for r in range(Row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "\n",
    "        return board\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0]) \n",
    "        vis1 = [[0] * n for _ in range(m)]\n",
    "        vis2 = [[0] * n for _ in range(m)]\n",
    "        while True:\n",
    "            flag = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue \n",
    "                    if not vis1[i][j]:\n",
    "                        tot= 1\n",
    "                        for k in range(j+1, n):\n",
    "                            if board[i][k] == board[i][k-1]:\n",
    "                                tot += 1\n",
    "                            else:\n",
    "                                break \n",
    "                        if tot >= 3:\n",
    "                            flag = 1\n",
    "                            for k in range(j, j+tot):\n",
    "                                vis1[i][k] = 1 \n",
    "                    if not vis2[i][j]:\n",
    "                        tot = 1 \n",
    "                        for k in range(i+1, m):\n",
    "                            if board[k][j] == board[k-1][j]:\n",
    "                                tot += 1\n",
    "                            else:\n",
    "                                break \n",
    "                        if tot >= 3:\n",
    "                            flag = 1\n",
    "                            for k in range(i, i+tot):\n",
    "                                vis2[k][j] = 1\n",
    "            #print(flag)\n",
    "            if flag == 0:\n",
    "                break \n",
    "            for j in range(n):\n",
    "                l = m-1\n",
    "                for r in range(m-1, -1, -1):\n",
    "                    if vis1[r][j] or vis2[r][j]:\n",
    "                        vis1[r][j] = vis2[r][j] = 0\n",
    "                        continue \n",
    "                    else:\n",
    "                        board[l][j] = board[r][j]\n",
    "                        l -= 1\n",
    "                while l >= 0:\n",
    "                    board[l][j] = 0\n",
    "                    l-=1 \n",
    "        return board \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1,-1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for w in range(wr,-1,-1):\n",
    "                board[w][c] = 0\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i][j1]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def crush():\n",
    "            to_crush = set()\n",
    "            # 行\n",
    "            for i in range(m):\n",
    "                j1, j2 = 0, 0\n",
    "                while j2 <= n:\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1] > 0:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.add((i, k))\n",
    "                        j1 = j2\n",
    "                    j2 += 1\n",
    "            # 列\n",
    "            for j in range(n):\n",
    "                i1, i2 = 0, 0\n",
    "                while i2 <= m:\n",
    "                    if i2 == m or board[i1][j] != board[i2][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j] > 0:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.add((k, j))\n",
    "                        i1 = i2\n",
    "                    i2 += 1\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = len(board), len(board[0])\n",
    "        todo = True\n",
    "\n",
    "        while todo:\n",
    "            todo = False\n",
    "            # row judge\n",
    "            for i in range(row):\n",
    "                for j in range(col-2):\n",
    "                    if board[i][j] != 0 and abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2]):\n",
    "                        todo = True\n",
    "                        tmp = - abs(board[i][j])\n",
    "                        board[i][j] = tmp\n",
    "                        board[i][j+1] = tmp\n",
    "                        board[i][j+2] = tmp\n",
    "\n",
    "            # col judge\n",
    "            for j in range(col):\n",
    "                for i in range(row-2):\n",
    "                    if board[i][j] != 0 and abs(board[i][j]) == abs(board[i+1][j]) == abs(board[i+2][j]):\n",
    "                        todo = True\n",
    "                        tmp = - abs(board[i][j])\n",
    "                        board[i][j] = tmp\n",
    "                        board[i+1][j] = tmp\n",
    "                        board[i+2][j] = tmp\n",
    "\n",
    "            #fall as cols\n",
    "            if todo:\n",
    "                for j in range(col):\n",
    "                    waitRow = row - 1\n",
    "                    for i in range(row-1, -1, -1):\n",
    "                        if board[i][j] > 0:\n",
    "                            board[waitRow][j] = board[i][j]\n",
    "                            waitRow -= 1\n",
    "                    while waitRow > -1:\n",
    "                        board[waitRow][j] = 0\n",
    "                        waitRow -= 1\n",
    "\n",
    "        return board\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R,C= len(board),len(board[0])\n",
    "        #check horizontal same\n",
    "        crashed= False\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c])==abs(board[r][c+1])==abs(board[r][c+2])!=0:\n",
    "                    board[r][c]=board[r][c+1]=board[r][c+2]=-abs(board[r][c])\n",
    "                    crashed=True\n",
    "        #check vertical same\n",
    "        for c in range(C):\n",
    "            for r in range(R-2):\n",
    "                if abs(board[r][c])==abs(board[r+1][c])==abs(board[r+2][c])!=0:\n",
    "                    board[r][c]=board[r+1][c]=board[r+2][c]=-abs(board[r][c])\n",
    "                    crashed= True\n",
    "\n",
    "        for c in range(C):\n",
    "            write=R-1\n",
    "            for read in range(R-1,-1,-1):\n",
    "                newValue= board[read][c]\n",
    "                board[read][c]=0\n",
    "                if newValue>0:\n",
    "                    board[write][c]= newValue\n",
    "                    write-=1\n",
    "            # for write in range(write,-1,-1):\n",
    "            #     board[write][c]=0\n",
    "        if crashed:\n",
    "            return self.candyCrush(board)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        mark = True\n",
    "        while mark:\n",
    "            # 标记需要粉碎的糖果\n",
    "            mark = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if j < n - 2 and abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2]):\n",
    "                        mark = True\n",
    "                        val = abs(board[i][j])\n",
    "                        board[i][j] = -val\n",
    "                        board[i][j+1] = -val\n",
    "                        board[i][j+2] = -val\n",
    "                    if i < m - 2 and abs(board[i][j]) == abs(board[i+1][j]) == abs(board[i+2][j]):\n",
    "                        mark = True\n",
    "                        val = abs(board[i][j])\n",
    "                        board[i][j] = -val\n",
    "                        board[i+1][j] = -val\n",
    "                        board[i+2][j] = -val\n",
    "            # 糖果下落\n",
    "            for j in range(n):\n",
    "                idx = m - 1\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] > 0:\n",
    "                        board[idx][j] = board[i][j]\n",
    "                        idx -= 1\n",
    "                for i in range(idx, -1, -1):\n",
    "                    board[i][j] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R,C= len(board),len(board[0])\n",
    "        #check horizontal same\n",
    "        crashed= False\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c])==abs(board[r][c+1])==abs(board[r][c+2])!=0:\n",
    "                    board[r][c]=board[r][c+1]=board[r][c+2]=-abs(board[r][c])\n",
    "                    crashed=True\n",
    "        #check vertical same\n",
    "        for c in range(C):\n",
    "            for r in range(R-2):\n",
    "                if abs(board[r][c])==abs(board[r+1][c])==abs(board[r+2][c])!=0:\n",
    "                    board[r][c]=board[r+1][c]=board[r+2][c]=-abs(board[r][c])\n",
    "                    crashed= True\n",
    "\n",
    "        for c in range(C):\n",
    "            write=R-1\n",
    "            for read in range(R-1,-1,-1):\n",
    "                if board[read][c]>0:\n",
    "                    board[write][c]= board[read][c]\n",
    "                    write-=1\n",
    "            for write in range(write,-1,-1):\n",
    "                board[write][c]=0\n",
    "        if crashed:\n",
    "            return self.candyCrush(board)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        def bfs(i, j):\n",
    "            v = board[i][j]\n",
    "            visited = set()\n",
    "            # Test row\n",
    "            row_candies = []\n",
    "            x = i\n",
    "            while x < m and board[x][j] == v:\n",
    "                row_candies.append((x, j))\n",
    "                x += 1\n",
    "            if len(row_candies) >= 3:\n",
    "                visited.update(row_candies)\n",
    "            # Test column\n",
    "            column_candies = []\n",
    "            y = j\n",
    "            while y < n and board[i][y] == v:\n",
    "                column_candies.append((i, y))\n",
    "                y += 1\n",
    "            if len(column_candies) >= 3:\n",
    "                visited.update(column_candies)\n",
    "            return visited\n",
    "\n",
    "        while True:\n",
    "            # Judge what grids will be crushed\n",
    "            drop = [[0] * n for _ in range(m)]\n",
    "            should_drop = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    visited = bfs(i, j)\n",
    "                    if len(visited) >= 3:\n",
    "                        for x, y in visited:\n",
    "                            drop[x][y] = 1\n",
    "                            should_drop = True\n",
    "            if not should_drop:\n",
    "                return board\n",
    "\n",
    "            # Crush and drop each column\n",
    "            for j in range(n):\n",
    "                bottom = m - 1\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    if drop[i][j] == 1:\n",
    "                        continue\n",
    "                    board[bottom][j] = board[i][j]\n",
    "                    bottom -= 1\n",
    "                while bottom != -1:\n",
    "                    board[bottom][j] = 0\n",
    "                    bottom -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        found = True\n",
    "\n",
    "        while found:\n",
    "            crush = [[0] * n for _ in range(m)]\n",
    "\n",
    "            for i in range(m):\n",
    "                for j in range(n - 2):\n",
    "                    if board[i][j] == board[i][j + 1] == board[i][j + 2] != 0:\n",
    "                        crush[i][j], crush[i][j + 1], crush[i][j + 2] = 1, 1, 1\n",
    "            \n",
    "            for i in range(m - 2):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == board[i + 1][j] == board[i + 2][j] != 0:\n",
    "                        crush[i][j], crush[i + 1][j], crush[i + 2][j] = 1, 1, 1\n",
    "            \n",
    "            # Crush\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if crush[i][j]:\n",
    "                        board[i][j] = 0\n",
    "            \n",
    "            # Drop\n",
    "            for j in range(n):\n",
    "                idx = m - 1\n",
    "                for i in reversed(range(m)):\n",
    "                    if board[i][j]:\n",
    "                        board[idx][j] = board[i][j]\n",
    "                        idx -= 1\n",
    "                for i in range(idx + 1):\n",
    "                    board[i][j] = 0\n",
    "            \n",
    "            found = any(crush[i][j] for i in range(m) for j in range(n))\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            mark = set()\n",
    "            ok = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0: continue\n",
    "                    if j + 2 < n and board[i][j] == board[i][j+1] == board[i][j+2]:\n",
    "                        ok = True\n",
    "                        mark.add((i,j))\n",
    "                        mark.add((i,j + 1))\n",
    "                        mark.add((i, j+ 2))\n",
    "                    if i + 2 < m and board[i][j] == board[i+1][j] == board[i + 2][j]:\n",
    "                        ok = True\n",
    "                        mark.add((i,j))\n",
    "                        mark.add((i + 1,j))\n",
    "                        mark.add((i + 2,j))\n",
    "            if not ok: break\n",
    "            nb = [[0] * n for _ in range(m)]\n",
    "            for j in range(n):\n",
    "                k = m - 1\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    if (i, j) not in mark:\n",
    "                        nb[k][j] =  board[i][j]\n",
    "                        k -= 1\n",
    "            board = nb\n",
    "        return board\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\"\"\"\n",
    "思路：\n",
    "1. 创建一个形状一样的board，用来记录是否需要消除\n",
    "2. 两轮循环，通过判断左右三个 + 上下三个是否相等来判断是否需要消除，并进行标记\n",
    "3. 根据标记的矩阵进行消除并填补新的元素，方法为不断向上查找第一个不为0的元素，然后将其下移\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        def check_more2go(board, check):\n",
    "            flag = False\n",
    "            for i in range(1, m-1):\n",
    "                for j in range(0, n):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i-1][j] == board[i][j] == board[i+1][j]:\n",
    "                        check[i-1][j] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i+1][j] = True\n",
    "                        flag = True\n",
    "\n",
    "            for i in range(0, m):\n",
    "                for j in range(1, n-1):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i][j-1] == board[i][j] == board[i][j+1]:\n",
    "                        check[i][j-1] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i][j+1] = True\n",
    "                        flag = True\n",
    "            return flag\n",
    "\n",
    "        while True:\n",
    "            check = [[False] * n for _ in range(m)]\n",
    "            if not check_more2go(board, check):\n",
    "                return board\n",
    "            print(check)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if check[i][j]:\n",
    "                        board[i][j] = 0\n",
    "            print(board)\n",
    "            \n",
    "            # 模拟下坠\n",
    "            for i in range(m-1, -1, -1):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        for k in range(i-1, -1, -1):\n",
    "                            if board[k][j] != 0:\n",
    "                                board[i][j] = board[k][j]\n",
    "                                board[k][j] = 0\n",
    "                                break\n",
    "            print(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            vis = set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] != 0 and board[i][j] not in vis:\n",
    "                        v = board[i][j]\n",
    "                        x, y = j - 1, j + 1\n",
    "                        while x >= 0 and board[i][x] == v:\n",
    "                            x -= 1\n",
    "                        while y < n and board[i][y] == v:\n",
    "                            y += 1\n",
    "                        cnt = y - x - 1\n",
    "                        if cnt >= 3:\n",
    "                            for k in range(x + 1, y):\n",
    "                                vis.add((i, k))\n",
    "\n",
    "                        \n",
    "                        v = board[i][j]\n",
    "                        x, y = i - 1, i + 1\n",
    "                        while x >= 0 and board[x][j] == v:\n",
    "                            x -= 1\n",
    "                        while y < m and board[y][j] == v:\n",
    "                            y += 1\n",
    "                        cnt = y - x - 1\n",
    "                        if cnt >= 3:\n",
    "                            for k in range(x + 1, y):\n",
    "                                vis.add((k, j))\n",
    "            if len(vis) == 0: return board\n",
    "            for x, y in vis:\n",
    "                board[x][y] = 0  # 这里已经对网格里面的进行了更新\n",
    "            for j in range(n):   # 考虑每一列\n",
    "                a = []\n",
    "                for i in range(m - 1, -1, -1):  # 倒序遍历行，因为上面的要填到下面\n",
    "                    if board[i][j]:             # 如果有数值代表有糖果\n",
    "                        a.append(board[i][j])\n",
    "                    board[i][j] = 0             # 将这列的全部置0\n",
    "                k = len(a)                      # 这个代表这列一共有多少位置有糖果\n",
    "                for i in range(m - 1, m - k - 1, -1):  # 依然从倒序遍历，但填数字的上限在 m - k - 1，之后上面就都是没有糖果的了\n",
    "                    board[i][j] = a[m - i - 1]\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = set()\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.add((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.add((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            rem = []\n",
    "            # 水平\n",
    "            for i in range(m):\n",
    "                pre = board[i][0]\n",
    "                cnt = 1\n",
    "                for j in range(1, n):\n",
    "                    if pre == board[i][j]:\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        if cnt >= 3 and pre:\n",
    "                            rem.extend([i, k] for k in range(j - cnt, j))\n",
    "                        cnt = 1\n",
    "                        pre = board[i][j]\n",
    "                if cnt >= 3 and pre:\n",
    "                    rem.extend([i, k] for k in range(n - cnt, n))\n",
    "            # 竖直\n",
    "            for j in range(n):\n",
    "                pre = board[0][j]\n",
    "                cnt = 1\n",
    "                for i in range(1, m):\n",
    "                    if pre == board[i][j]:\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        if cnt >= 3 and pre:\n",
    "                            rem.extend([k, j] for k in range(i - cnt, i))\n",
    "                        cnt = 1\n",
    "                        pre = board[i][j]\n",
    "                if cnt >= 3 and pre:\n",
    "                    rem.extend([k, j] for k in range(m - cnt, m))\n",
    "\n",
    "            if rem:\n",
    "                \n",
    "                flag = True\n",
    "                for i, j in rem:\n",
    "                    board[i][j] = 0\n",
    "                \n",
    "                # 移动值\n",
    "                for j in range(n):\n",
    "                    lst = []\n",
    "                    for i in range(m - 1, -1, -1):\n",
    "                        if board[i][j]:\n",
    "                            lst.append(board[i][j])\n",
    "                        board[i][j] = 0\n",
    "                    k = len(lst)\n",
    "                    for i in range(m - 1, m - k - 1, -1):\n",
    "                        board[i][j] = lst[m - 1 - i]\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        waitdelete = []\n",
    "        m, n = len(board), len(board[0])\n",
    "        def cancle(i,j):\n",
    "            curEle = board[i][j]\n",
    "            # go right\n",
    "            if curEle == 0:\n",
    "                return\n",
    "            if j < n-2:\n",
    "                idx = 0\n",
    "                while idx < n-j:\n",
    "                    if board[i][j+idx] == curEle:\n",
    "                        idx += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if idx >= 3:\n",
    "                    for i1 in range(idx):\n",
    "                        waitdelete.append((i,j+i1))\n",
    "            \n",
    "            # go down\n",
    "            if i < m-2:\n",
    "                jdx = 0\n",
    "                while jdx < m-i:\n",
    "                    if board[i+jdx][j] == curEle:\n",
    "                        jdx += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if jdx >= 3:\n",
    "                    for j1 in range(jdx):\n",
    "                        waitdelete.append((i+j1,j))\n",
    "        def runDown():\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        zerolen = 0\n",
    "                        while i-zerolen>= 0 and board[i-zerolen][j] == 0:\n",
    "                            zerolen += 1\n",
    "                        for ss in range(i-zerolen+1):\n",
    "                            board[i-ss][j] = board[i-ss-zerolen][j]\n",
    "                        for ss in range(zerolen):\n",
    "                            board[ss][j] = 0\n",
    "            return \n",
    "\n",
    "\n",
    "\n",
    "        needRun = True\n",
    "        while needRun:\n",
    "            # print(\"==============\")\n",
    "            # for line in board:\n",
    "            #     print(line)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    cancle(i,j)\n",
    "            # print(waitdelete)\n",
    "            if len(waitdelete) == 0:\n",
    "                return board\n",
    "            for ele in waitdelete:\n",
    "                board[ele[0]][ele[1]] = 0\n",
    "            \n",
    "            waitdelete.clear()\n",
    "            runDown()\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\r\n",
    "        Row, Col = len(board), len(board[0])\r\n",
    "        need_todo = True\r\n",
    "        ################ 注意L形也是可以的\r\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\r\n",
    "            need_todo = False\r\n",
    "            #### 先搞定行\r\n",
    "            for r in range(Row):\r\n",
    "                for c in range(Col - 2):\r\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\r\n",
    "                        need_todo = True\r\n",
    "                        tmp = - abs(board[r][c])\r\n",
    "                        board[r][c]   = tmp\r\n",
    "                        board[r][c+1] = tmp\r\n",
    "                        board[r][c+2] = tmp\r\n",
    "            #### 再搞定列\r\n",
    "            for c in range(Col):\r\n",
    "                for r in range(Row - 2):\r\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\r\n",
    "                        need_todo = True\r\n",
    "                        tmp = -abs(board[r][c])\r\n",
    "                        board[r][c]   = tmp\r\n",
    "                        board[r+1][c] = tmp\r\n",
    "                        board[r+2][c] = tmp\r\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\r\n",
    "            if need_todo == True:\r\n",
    "                for c in range(Col):\r\n",
    "                    rr = Row - 1\r\n",
    "                    for r in range(Row - 1, -1, -1):\r\n",
    "                        if board[r][c] > 0:\r\n",
    "                            board[rr][c] = board[r][c]\r\n",
    "                            rr -= 1\r\n",
    "                    while rr > -1:\r\n",
    "                        board[rr][c] = 0\r\n",
    "                        rr -= 1\r\n",
    "\r\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "\n",
    "        remove = [[False] * m for _ in range(n)]\n",
    "        todo = True\n",
    "        # first mark the elements to be eliminated horizontally\n",
    "        while todo:\n",
    "            todo = False\n",
    "            for r in range(n):\n",
    "                left = 0\n",
    "                right = 0\n",
    "                while left < m:\n",
    "                    while right < m and board[r][left] == board[r][right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right - left >= 3 and board[r][left] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(left, right):\n",
    "                            remove[r][idx] = True\n",
    "                    left = right\n",
    "    \n",
    "            # second mark the elements to be eliminated vertically\n",
    "            for c in range(m):\n",
    "                up = 0\n",
    "                down = 0\n",
    "                while up < n:\n",
    "                    while down < n and board[up][c] == board[down][c]:\n",
    "                        down += 1\n",
    "                    \n",
    "                    if down - up >= 3 and board[up][c] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(up, down):\n",
    "                            remove[idx][c] = True\n",
    "                    up = down\n",
    "            \n",
    "            # vertically squash every removed element row by row from bottom to top\n",
    "            for r in range(n - 1, -1, -1):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        index = r\n",
    "                        while index >= 0 and remove[index][c]:\n",
    "                            index -= 1\n",
    "                        if index >= 0:\n",
    "                            board[r][c] = board[index][c]\n",
    "                            remove[r][c] = False\n",
    "                            remove[index][c] = True\n",
    "            \n",
    "            for r in range(n):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        board[r][c] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = set()\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.add((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.add((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\"\"\"\n",
    "思路：\n",
    "1. 创建一个形状一样的board，用来记录是否需要消除\n",
    "2. 两轮循环，通过判断左右三个 + 上下三个是否相等来判断是否需要消除，并进行标记\n",
    "3. 根据标记的矩阵进行消除并填补新的元素，方法为不断向上查找第一个不为0的元素，然后将其下移\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        def check_more2go(board, check):\n",
    "            flag = False\n",
    "            for i in range(1, m-1):\n",
    "                for j in range(0, n):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i-1][j] == board[i][j] == board[i+1][j]:\n",
    "                        check[i-1][j] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i+1][j] = True\n",
    "                        flag = True\n",
    "\n",
    "            for i in range(0, m):\n",
    "                for j in range(1, n-1):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i][j-1] == board[i][j] == board[i][j+1]:\n",
    "                        check[i][j-1] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i][j+1] = True\n",
    "                        flag = True\n",
    "            return flag\n",
    "\n",
    "        while True:\n",
    "            check = [[False] * n for _ in range(m)]\n",
    "            if not check_more2go(board, check):\n",
    "                return board\n",
    "            print(check)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if check[i][j]:\n",
    "                        board[i][j] = 0\n",
    "            print(board)\n",
    "            \n",
    "            # 模拟下坠\n",
    "            # 必须从最后一行开始\n",
    "            for i in range(m-1, -1, -1):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        for k in range(i-1, -1, -1):\n",
    "                            if board[k][j] != 0:\n",
    "                                board[i][j] = board[k][j]\n",
    "                                board[k][j] = 0\n",
    "                                break\n",
    "            print(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def check():\n",
    "            state = [[0] * n for _ in range(m)]\n",
    "            signal = 0\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n - 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur != 0 and cur == board[i][j + 1] and cur == board[i][j + 2]:\n",
    "                        signal = 1\n",
    "                        state[i][j:j+3] = [1]*3\n",
    "                        j += 2\n",
    "                        while j + 1 < n and board[i][j + 1] == board[i][j]:\n",
    "                            state[i][j + 1] = 1\n",
    "                            j += 1\n",
    "                    j += 1\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                while i >= 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur == 0:\n",
    "                        break\n",
    "                    if cur == board[i - 1][j] and cur == board[i - 2][j]:\n",
    "                        signal = 1\n",
    "                        for x in range(i, i - 3, -1):\n",
    "                            state[x][j] = 1\n",
    "                        i -= 2\n",
    "                        while i >= 1 and board[i - 1][j] == board[i][j]:\n",
    "                            state[i - 1][j] = 1\n",
    "                            i -= 1\n",
    "                    i -= 1\n",
    "            return state, signal\n",
    "        \n",
    "        def revise(state):\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                pos = m - 1\n",
    "                while pos >= 0:\n",
    "                    if state[pos][j] != 1:\n",
    "                        board[i][j] = board[pos][j]\n",
    "                        i -= 1\n",
    "                    pos -= 1\n",
    "                while i >= 0:\n",
    "                    board[i][j] = 0\n",
    "                    i -= 1\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            sta, sig = check()\n",
    "            if sig == 0:\n",
    "                return board\n",
    "            revise(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        boom = [[False]*n for _ in range(m)]\n",
    "\n",
    "        def update():\n",
    "            stable = True\n",
    "\n",
    "            # 获取待粉碎的糖果\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n:\n",
    "                    if board[i][j] == 0:\n",
    "                        j += 1\n",
    "                        continue\n",
    "                    k = j + 1\n",
    "                    while k < n and board[i][k] == board[i][j]:\n",
    "                        k += 1\n",
    "                    if k - j >= 3:\n",
    "                        stable = False\n",
    "                        for jj in range(j, k):\n",
    "                            boom[i][jj] = True\n",
    "                    j = k\n",
    "            for j in range(n):\n",
    "                i = 0\n",
    "                while i < m:\n",
    "                    if board[i][j] == 0:\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    k = i + 1\n",
    "                    while k < m and board[k][j] == board[i][j]:\n",
    "                        k += 1\n",
    "                    if k - i >= 3:\n",
    "                        stable = False\n",
    "                        for ii in range(i, k):\n",
    "                            boom[ii][j] = True\n",
    "                    i = k\n",
    "            \n",
    "            if stable:\n",
    "                return\n",
    "\n",
    "            # 更新\n",
    "            for j in range(n):\n",
    "                i0 = i1 = m - 1\n",
    "                while i1 >= 0:\n",
    "                    if boom[i1][j]:\n",
    "                        i1 -= 1\n",
    "                        continue\n",
    "                    board[i0][j] = board[i1][j]\n",
    "                    i0 -= 1\n",
    "                    i1 -= 1\n",
    "                for i1 in range(i0, -1, -1):\n",
    "                    board[i1][j] = 0\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    boom[i][j] = False\n",
    "            update()\n",
    "        \n",
    "        update()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param board:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def detect_to_remove(b1):\n",
    "            rmidx = set()\n",
    "            for k,v in enumerate(b1):\n",
    "                for k2,v2 in enumerate(v):\n",
    "                    if v2 == 0:\n",
    "                        continue\n",
    "                    dq1 = deque()\n",
    "                    dq1.append((k,k2))\n",
    "                    used = set()\n",
    "                    while dq1:\n",
    "                        idx1 = dq1.popleft()\n",
    "                        dict1 = [(0,1), (0, -1)]\n",
    "                        if idx1 in used:\n",
    "                            continue\n",
    "                        used.add(idx1)\n",
    "                        for i in dict1:\n",
    "                            newidx = idx1[0] + i[0], idx1[1] + i[1]\n",
    "                            if 0 <= newidx[0] < len(b1) and 0 <= newidx[1] < len(b1[0]) and b1[newidx[0]][newidx[1]] == v2:\n",
    "                                dq1.append(newidx)\n",
    "                    if len(used) >= 3:\n",
    "                        for i in used:\n",
    "                            rmidx.add(i)\n",
    "\n",
    "                    dq1 = deque()\n",
    "                    dq1.append((k, k2))\n",
    "                    used = set()\n",
    "                    while dq1:\n",
    "                        idx1 = dq1.popleft()\n",
    "                        dict1 = [(1, 0), (-1, 0)]\n",
    "                        if idx1 in used:\n",
    "                            continue\n",
    "                        used.add(idx1)\n",
    "                        for i in dict1:\n",
    "                            newidx = idx1[0] + i[0], idx1[1] + i[1]\n",
    "                            if 0 <= newidx[0] < len(b1) and 0 <= newidx[1] < len(b1[0]) and b1[newidx[0]][\n",
    "                                newidx[1]] == v2:\n",
    "                                dq1.append(newidx)\n",
    "                    if len(used) >= 3:\n",
    "                        for i in used:\n",
    "                            rmidx.add(i)\n",
    "\n",
    "            return rmidx\n",
    "\n",
    "\n",
    "        def adjust_board(id_list, b1):\n",
    "            for i in id_list:\n",
    "                b1[i[0]][i[1]] = 0\n",
    "            new_m = []\n",
    "            for i in range(len(b1[0])):\n",
    "                newl = []\n",
    "                for j in range(len(b1)):\n",
    "                    if b1[j][i] != 0:\n",
    "                        newl.append(b1[j][i])\n",
    "                while len(newl) < len(b1):\n",
    "                    newl.insert(0, 0)\n",
    "                new_m.append(newl)\n",
    "            for i in range(len(new_m)):\n",
    "                for j in range(len(new_m[0])):\n",
    "                    b1[j][i] = new_m[i][j]\n",
    "\n",
    "\n",
    "        def get_cmp(cur, ll):\n",
    "            idx = 0\n",
    "            for i in ll:\n",
    "                if i > cur:\n",
    "                    idx += 1\n",
    "            return idx\n",
    "\n",
    "        while True:\n",
    "            v1 = detect_to_remove(board)\n",
    "            if len(v1) == 0:\n",
    "                break\n",
    "            adjust_board(v1, board)\n",
    "        return board\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
